package com.sicheng.lc.lc笔试.腾讯篇;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/14 12:06
 */
@SuppressWarnings("all")
public class 看不见的楼层_单调栈 {
    /**
     * 题目描述
     * 小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。
     * 小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？
     * （当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）
     * <p>
     * 输入描述:
     * 输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。
     * 1<=n<=100000;
     * 1<=wi<=100000;
     * <p>
     * 输出描述:
     * 输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。
     * <p>
     * 输入例子1:
     * 6
     * 5 3 8 3 2 5
     * <p>
     * 输出例子1:
     * 3 3 5 4 4 4
     * <p>
     * 例子说明1:
     * 当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
//        赋值
        for (int i = 0; i < n; i++)
            nums[i] = scanner.nextInt();
//        给定2个堆栈：分别向左边右边看齐
        Deque<Integer> left_stack = new ArrayDeque<>();
        Deque<Integer> right_stack = new ArrayDeque<>();
//        向左看和向右看的楼的数量
        int[] left_count = new int[n], right_count = new int[n];
        int j;
        for (int i = 0; i < n; i++) {
//            从右边到左边看
            j = n - i - 1;
            left_count[i] = left_stack.size();
            right_count[j] = right_stack.size();
//            如果当前的数字比栈顶的数字还要大的话，就出栈，因为已经被挡住了
            while (!left_stack.isEmpty() && left_stack.peek() <= nums[i])
                left_stack.pop();
            while (!right_stack.isEmpty() && right_stack.peek() <= nums[j])
                right_stack.pop();
            left_stack.push(nums[i]);
            right_stack.push(nums[j]);
        }
        for (int i = 0; i < n; i++)
            System.out.print(left_count[i] + right_count[i] + 1 + " ");
        System.out.println();
    }

    //残次品
    private static void notFinished() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        //存储 索引位置的元素挤掉的元素个数
        HashMap<Integer, Integer> out = new HashMap<>();
        //每轮正在挤掉的个数

        int[] res = new int[n];
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                int first = 0;
                int index = stack.poll();
                count++;
                if (!stack.isEmpty()) first = 1;
                // 看到自己，看到自己怼掉的元素，看到怼掉自己的元素
                res[index] = count + out.getOrDefault(index, 0) + first + 1;
            }
            out.put(i, count);
            stack.push(i);
        }
    }

}

